#ifndef _BFS_HH_
#define _BFS_HH_
#include "State.h"
#include <queue>
#include <utility>

///
/// Breadth first Search generic template
///
/// Calls __action for each __valid_position in BFS order
///
template<typename _Action, typename _Condition>
void breadth_first_search( State & state, Location sLoc, _Action __action, _Condition __valid_position)
{
  std::vector<std::vector<bool> > visited(state.rows, std::vector<bool>(state.cols, 0));
  std::queue< std::pair<Location, unsigned> > locQueue;
  
  locQueue.push(std::make_pair(sLoc, 0));

  while(!locQueue.empty())
    {
      std::pair<Location, unsigned> p = locQueue.front();
      locQueue.pop();
      Location cLoc = p.first;
      unsigned depth = p.second;

      if(!__action(state,sLoc,cLoc,depth)) return;

      for(int d=0; d<TDIRECTIONS; d++)
	{
	  Location nLoc = state.getLocation(cLoc, d);
	  if(!visited[nLoc.row][nLoc.col] and __valid_position(state,sLoc,nLoc,depth))
	    {
	      locQueue.push(std::make_pair(nLoc,depth+1));
	    }
	  visited[nLoc.row][nLoc.col] = 1;
	}
    }
}


/// Functor for flying potentials
/// i.e. do not avoid water
struct valid_for_flying_t
{
  double radius;

  valid_for_flying_t(double _radius) : radius(_radius) {}

  bool operator()(State & state, const Location & sLoc, const Location & nLoc, unsigned depth)
  {
    return state.distance(sLoc,nLoc) <= radius;
  }
};

/// Functor for direct walking potentials
/// i.e. do not avoid dangerous positions
struct valid_for_walking_t
{
  unsigned distance;

  valid_for_walking_t(unsigned _distance) : distance(_distance) {}

  bool operator()(State & state, const Location & sLoc, const Location & nLoc, unsigned depth)
  {
    return !state.location(nLoc).isWater and depth < distance;
  }
};


/// Functor for safe walking potentials
/// i.e. avoid dangerous positions
struct valid_for_safe_walking_t
{
  unsigned distance;

  valid_for_safe_walking_t(unsigned _distance) : distance(_distance) {}

  bool operator()(State & state, const Location & sLoc, const Location & nLoc, unsigned depth)
  {
    return !state.location(nLoc).isWater and state.location(nLoc).isSafe and depth < distance;
  }
};



///
/// Flying BFS template
///
template<typename _Action>
void fly( State & state, Location sLoc, double radius,  _Action __action)
{
  valid_for_flying_t valid2fly(radius);
  breadth_first_search(state, sLoc, __action, valid2fly);
}


///
/// Walking BFS template
///
template<typename _Action>
void walk( State & state, Location sLoc, unsigned distance, _Action __action)
{
  valid_for_walking_t valid2walk(distance);
  breadth_first_search(state, sLoc, __action, valid2walk);
}


///
/// Safe Walking BFS template
///
template<typename _Action>
void safe_walk( State & state, Location sLoc, unsigned distance, _Action __action)
{
  valid_for_safe_walking_t valid4safe_walk(distance);
  breadth_first_search(state, sLoc, __action, valid4safe_walk);
}



#endif /* _BFS_HH_ */
